#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <cstdlib>
#include <fstream>

using namespace std;

struct arc{
	int node1;
	int node2;
	int value;
	bool isLeaf;
	int father;
	int tabooTenure;
	int frequency;
};

class graph {
	private:
	public:
		vector<arc> qGraph;
		vector<arc>::iterator qGraphIt;
		graph(char* fname) {
			fstream benchmarkFile;
			arc tmp;
			string str, str2;
			int pos, pos2, l=1;
			
			benchmarkFile.open(fname, fstream::in);
			if(!benchmarkFile.is_open()){
				cout << "It hasn't been possible to open the file. Sorry :(" << endl;
				exit(0);														   
			}
			while(getline(benchmarkFile,str)){
				if(l==1 || l==2){
					l++;
					continue;
				}
				pos=str.find_first_of(" ");
				str2 = str.substr(0,pos);
				tmp.node1 = atoi(str2.c_str());
				pos2=str.find_last_of(" ");
				str2 = str.substr(pos,pos2);
				tmp.node2 = atoi(str2.c_str());
				pos=str.size();
				str2 = str.substr(pos2,pos);
				tmp.value = atoi(str2.c_str());
				tmp.isLeaf = false;
				tmp.father = 0;
				tmp.tabooTenure=0;
				tmp.frequency=0;
				qGraph.push_back(tmp);
			}
			benchmarkFile.close();
		}
		
		vector<arc> getArcs(int node) {
			vector<arc> arcVector;	
			arc tmp;
			for(qGraphIt = qGraph.begin(); qGraphIt < qGraph.end(); qGraphIt++){
				tmp = *qGraphIt;
				if(tmp.node1 == node || tmp.node2 == node){
					arcVector.push_back(tmp);
				}
			}
			return arcVector;
		}		
};

class kTree {
	private:
		int k;
	public:
		vector<arc> arcVector;
		vector<arc>::iterator itArc;
		int value, modifiedValue;
		arc removedArc;
		bool taboo;

		kTree(int k,graph g) {
			this->k = k;
			arc tmp, tmp2;
			int father, i=0, fathertmp;
			vector<arc> possibleArcs;
			vector<int> fathers;
			vector<int>::iterator fathersIt;
			bool exist=false;
			
			tmp = g.qGraph[0];
			tmp.father=tmp.node1;
			father=tmp.node1;
			fathers.push_back(father);
			tmp.isLeaf=true;
			arcVector.push_back(tmp);
			possibleArcs = g.getArcs(tmp.node1);
			while(i<k-2){
				if(!possibleArcs.empty()){
					tmp = possibleArcs.back();
					for(itArc = arcVector.begin(); itArc < arcVector.end(); itArc++){
						tmp2 = *itArc;
						if(tmp2.node1 == tmp.node1 && tmp2.node2 == tmp.node2) exist=true;
					}
					for(fathersIt = fathers.begin(); fathersIt < fathers.end(); fathersIt++){
						fathertmp = *fathersIt;
						if(tmp.node2 == fathertmp) exist=true;
					}	
					if(!exist){
						tmp.father = father;
						tmp.isLeaf = true;
						arcVector.push_back(tmp);
						i++;
					}
					else{
						tmp = arcVector.back();
						exist=false;
					}
					possibleArcs.pop_back();
				}
				else{
					if(father==tmp.node1){
						possibleArcs = g.getArcs(tmp.node2);
						father=tmp.node2;
						fathers.push_back(father);
					}
					else{
						possibleArcs = g.getArcs(tmp.node1);
						father=tmp.node1;
						fathers.push_back(father);
					}
				}
			}
			for(fathersIt = fathers.begin(); fathersIt < fathers.end(); fathersIt++){
				fathertmp = *fathersIt;
				for(itArc = arcVector.begin(); itArc < arcVector.end(); itArc++){
					tmp2 = *itArc;
					if(tmp2.node2 == fathertmp){
						tmp2.isLeaf = false;
						arcVector.erase(itArc);
						arcVector.push_back(tmp2);
					} 
				}
			}
		}	

		/*
		 * Second constructor
		 * Receives an arc vector
		 */
		kTree(vector<arc> arcV) {
			arcVector = arcV;
			itArc = arcVector.end();
		}
		
		/*
		 * Calculates value, sets it
		 */
		void refreshValue() {
			int acum = 0;
			arc aux;
			for (itArc = arcVector.begin(); itArc < arcVector.end(); itArc++) {
				aux = *itArc;
				acum += aux.value;
			}
			value = acum;
		}

		vector<arc> getLeaves() {
			vector<arc> arcV;
			arc aux;
			for (itArc = arcVector.begin(); itArc < arcVector.end(); itArc++) {
				aux = *itArc;

				if(aux.isLeaf == true){
					arcV.push_back(aux);
				}
			}
			return arcV;
		}

		vector<arc> getRemainingArcs(arc leaf) {
			vector<arc> others = arcVector;
			vector<arc>::iterator othersIt;
			arc tmp;
			for (othersIt = others.begin(); othersIt < others.end(); othersIt++) {
				tmp = *othersIt;
				if(tmp.node1 == leaf.node1 && tmp.node2 == leaf.node2){
					others.erase(othersIt);
					break;
				}
			}
			return others;
		}

		int getModifiedValue(float factor) {
			return (int) (value + (factor*removedArc.frequency));
		}
};

class minValue{
	public:
		bool operator() (const kTree& first, const kTree& second) const{
			return (first.value)>(second.value);
		}
};

priority_queue<kTree, vector<kTree>, minValue> neighbors;

void getNeighbors(kTree searchTree, graph theGraph) { 
	vector<arc> leaves = searchTree.getLeaves();
	vector<arc>::iterator itLeaves;
	vector<arc> others;
	vector<arc> newOthers;
	vector<arc>::iterator itOthers;
	vector<arc> possibleArcs;
	vector<arc>::iterator possIt;
	arc leaf, aux, tmp, arcNode;
	int tmpNode, thisNode;
	bool exist1=false, exist2=false, cicle=false;
	vector<int> revised;
	vector<int>::iterator itRevised;
	vector<int> nodes;
	vector<int>::iterator itNodes;
	vector<kTree> trees;
	vector<kTree>::iterator itTrees;

	for(itLeaves = leaves.begin(); itLeaves < leaves.end(); itLeaves++) {
		leaf = *itLeaves;
		others = searchTree.getRemainingArcs(leaf);
		for(itOthers = others.begin(); itOthers < others.end(); itOthers++){
			arcNode = *itOthers;
			nodes.push_back(arcNode.node1);
			nodes.push_back(arcNode.node2);
		}
		revised.clear();
		
		for(itOthers = others.begin(); itOthers < others.end(); itOthers++) {
			aux = *itOthers;
			for(itRevised = revised.begin(); itRevised < revised.end();itRevised++){
				tmpNode = *itRevised;
				if(tmpNode == aux.node1) exist1 = true;
				if(tmpNode == aux.node2) exist2 = true;
			}
			if(!exist1){
				possibleArcs = theGraph.getArcs(aux.node1);
				for(possIt=possibleArcs.begin();possIt<possibleArcs.end();possIt++){
					tmp = *possIt;
					if(aux.node1 == tmp.node1){
						for(itNodes=nodes.begin();itNodes<nodes.end();itNodes++){
							thisNode = *itNodes;
							if(tmp.node2 == thisNode) cicle = true;
						}
					}
					
					if(aux.node1 == tmp.node2){
						for(itNodes=nodes.begin();itNodes<nodes.end();itNodes++){
							thisNode = *itNodes;
							if(tmp.node1 == thisNode) cicle = true;
						}
					}
						
					if((tmp.node1 != aux.node1 || tmp.node2 != aux.node2) && !cicle){
						newOthers = others;
						newOthers.push_back(tmp);
						kTree tmpTree(newOthers);
						tmpTree.removedArc = leaf;
						if(tmp.tabooTenure > 0) tmpTree.taboo = true;
						tmpTree.refreshValue();
						neighbors.push(tmpTree);
					}
					cicle = false;
				}
				revised.push_back(aux.node1);
				exist1 = false;
				possibleArcs.clear();
			}
			if(!exist2){
				possibleArcs = theGraph.getArcs(aux.node2);
				for(possIt=possibleArcs.begin();possIt<possibleArcs.end();possIt++){
					tmp = *possIt;
					if(aux.node2 == tmp.node1){
						for(itNodes=nodes.begin();itNodes<nodes.end();itNodes++){
							thisNode = *itNodes;
							if(tmp.node2 == thisNode) cicle = true;
						}
					}
					
					if(aux.node2 == tmp.node2){
						for(itNodes=nodes.begin();itNodes<nodes.end();itNodes++){
							thisNode = *itNodes;
							if(tmp.node1 == thisNode) cicle = true;
						}
					}
					if((tmp.node1 != aux.node1 || tmp.node2 != aux.node2) && !cicle){
						newOthers = others;
						newOthers.push_back(tmp);
						kTree tmpTree(newOthers);
						tmpTree.removedArc = leaf;
						if(tmp.tabooTenure > 0) tmpTree.taboo = true;
						tmpTree.refreshValue();
						neighbors.push(tmpTree);
					}
					cicle = false;
				}
				revised.push_back(aux.node2);
				exist2 = false;
				possibleArcs.clear();
			}
		}
	}
}

int main(int argc, char *argv[]){
	/*setup*/
	int k = atoi(argv[1]);
	graph theGraph = graph::graph(argv[2]);
	float modifiedFactor = -.6;
	int tenure = 2;
	kTree alphaTree = kTree(k,theGraph); //the lowest cost solution
	kTree searchTree = alphaTree; //the current solution
	searchTree.refreshValue();

	//print initial tree
	for(searchTree.itArc = searchTree.arcVector.begin(); searchTree.itArc < searchTree.arcVector.end(); searchTree.itArc++) {
		arc pic = *searchTree.itArc;
		cout << pic.node1 << " " << pic.node2 << " " << pic.value << endl;
	}
	cout << "Value: " << searchTree.value << endl;
	cout << "<=================>" << endl;

	//criterio de paro: 4 iteraciones
	for (int ego = 0; ego < 4; ego++) {
		/*search*/
		getNeighbors(searchTree,theGraph);
	
		//we now have all the neighbors
		/*evaluation*/
		//taboo rule: a cut leaf cannot be added again for 2 iterations
		kTree topTree = neighbors.top();
		if (topTree.value < alphaTree.value) {
			//we have the best solution yet
			alphaTree = topTree;
			searchTree = topTree;
		} else {
			//ignore any taboo solutions from the queue and obtain the lowest modified value
			int lowestModified;
			int otherModified;

			//first neighbor
			if(topTree.removedArc.tabooTenure == 0) {
				lowestModified = topTree.getModifiedValue(modifiedFactor);			
			} else {
				lowestModified = 9999;
			}
			kTree bestTree = topTree;
			neighbors.pop();

			//the other neighbors
			while(!neighbors.empty()) {
				topTree = neighbors.top();	
				for (topTree.itArc = topTree.arcVector.begin(); topTree.itArc < topTree.arcVector.end(); topTree.itArc++) {	
					if(topTree.removedArc.tabooTenure == 0) {
						otherModified = topTree.getModifiedValue(modifiedFactor);
						if (otherModified < lowestModified) {
							lowestModified = otherModified;
							bestTree = topTree;
						}
					}
					neighbors.pop();
				}
			} 
			searchTree = bestTree;
		}

		//update arcs
		arc topArc;
		for(searchTree.itArc = searchTree.arcVector.begin(); searchTree.itArc < searchTree.arcVector.end(); searchTree.itArc++) {
			topArc = *searchTree.itArc;
			if(topArc.node1 == searchTree.removedArc.node1 && topArc.node2 == searchTree.removedArc.node2) {
				//mark the removed arc as taboo and update frequency
				topArc.tabooTenure = tenure;
				topArc.frequency++;
			} else if(topArc.tabooTenure > 0) {
				//update taboo arcs
				topArc.tabooTenure--;
			}
			cout << topArc.node1 << " " << topArc.node2 << " " << topArc.value << endl;
		}
		cout << "Value: " << searchTree.value << endl;
		cout << "<=================>" << endl;
		
	}
	cout << "Top value: " << alphaTree.value << endl;
	return 0;
}
